package com.cat.dynamicPlanning02;

/**
*   @description https://leetcode.cn/problems/n-queens-ii/
*   @author 曲大人的喵
*   @create 2025/11/5 21:50
*   @since JDK17
*/

public class Solution45 {
    boolean[] h = new boolean[10];
    int[] col = new int[10];
    boolean check(int x, int y) {
        if (h[y]) { // 该列已经填了
            return false;
        }
        for (int i = 0; i < x; i++) {
            if ((i - x == col[i] - y ) || (i + col[i] == x + y)) {
                return false;
            }
        }
        return true;
    }


    int dfs(int n, int r) {
        if (r == n) {
            return 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {   // 列
            if (check(r, i)) {
                h[i] = true;
                col[r] = i;
                ans += dfs(n, r + 1);
                h[i] = false;
            }
        }
        return ans;
    }
    public int totalNQueens(int n) {
        return dfs(n, 0);
    }
}
